
/**
 * 
 * 宜居星球改造计划
 * 
 * 题目描述

2XXX年，人类通过对火星的大气进行宜居改造分析，使得火星已在理论上具备人类宜居的条件；

由于技术原因，无法一次性将火星大气全部改造，只能通过局部处理形式；

假设将火星待改造的区域为row * column的网格，每个网格有3个值，宜居区、可改造区、死亡区，使用YES、NO、NA代替，YES表示该网格已经完成大气改造，NO表示该网格未进行改造，后期可进行改造，NA表示死亡区，不作为判断是否改造完的宜居，无法穿过；

初始化下，该区域可能存在多个宜居区，并目每个宜居区能同时在每个大阳日单位向上下左右四个方向的相邻格子进行扩散，自动将4个方向相邻的真空区改造成宜居区；

请计算这个待改造区域的网格中，可改造区是否能全部成宜居区，如果可以，则返回改造的大阳日天教，不可以则返回-1

输入描述
输入row * column个网格数据，每个网格值枚举值如下: YES，NO，NA；

样例:

YES YES NO
NO NO NO
NA NO YES
输出描述
可改造区是否能全部变成宜居区，如果可以，则返回改造的太阳日天数，不可以则返回-1。

备注
grid[i][j]只有3种情况，YES、NO、NA

row == grid.length
column == grid[i].length
1 ≤ row, column ≤ 8
用例
输入	YES YES NO
NO NO NO
YES NO NO
输出	2
说明	经过2个太阳日，完成宜居改造
输入	YES NO NO NO
NO NO NO NO
NO NO NO NO
NO NO NO NO
输出	6
说明	经过6个太阳日，可完成改造
输入	NO NA
输出	-1
说明	无改造初始条件，无法进行改造
输入	YES NO NO YES
NO NO YES NO
NO YES NA NA
YES NO NA NO
输出	-1
说明	-1 // 右下角的区域，被周边三个死亡区挡住，无法实现改造

 */

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;

/**
  * 
  题目解析
本题是图的多源BFS的经典题，解析可以参考：

计算疫情扩散时间-CSDN博客
https://blog.csdn.net/qfc_128220/article/details/127711317?ops_request_misc=%257B%2522request%255Fid%2522%253A%25220B6E9D85-0EFD-4396-81A2-6A115591D5C9%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=0B6E9D85-0EFD-4396-81A2-6A115591D5C9&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_ecpm_v1~rank_v31_ecpm-1-127711317-null-null.nonecase&utm_term=%E8%AE%A1%E7%AE%97%E7%96%AB%E6%83%85&spm=1018.2226.3001.4450

另外本题涉及不定行输入解析，可以看下：

ACM模式不定行输入获取-CSDN博客
https://fcqian.blog.csdn.net/article/details/132385403

  */
public class 宜居星球改造计划 {
   
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in).useDelimiter("[,\n]");
 
        ArrayList<String[]> matrix = new ArrayList<>();
        while (sc.hasNextLine()) {
            String lineStr = sc.nextLine();

            //System.out.println("接收参数---"+lineStr);
            if("".equals(lineStr)){

                break;
            }
            matrix.add(lineStr.split(" "));
        }
 
        System.out.println(bfs(matrix));
    }
 
    public static int bfs(ArrayList<String[]> matrix) {
        int row = matrix.size();
        int col = matrix.get(0).length;
 
        // 记录宜居取坐标位置
        LinkedList<Integer> queue = new LinkedList<>();
 
        // 记录可改造区数量
        int need = 0;
 
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                switch (matrix.get(i)[j]) {
                    case "YES":
                        queue.add(i * col + j);
                        break;
                    case "NO":
                        need++;
                        break;
                }
            }
        }
 
        // 如果没有宜居区，则无法改造，直接返回-1
        if (queue.isEmpty()) return -1;
 
        // 如果全是宜居区，则无需改造，直接返回0
        if (queue.size() == row * col) return 0;
 
        // 记录花费的天数
        int day = 0;
 
        // 上，下，左，右四个方向的偏移量
        int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
 
        // 图的多源BFS模板
        while (!queue.isEmpty() && need > 0) {
            // 当前层坐标数量
            int size = queue.size();
 
            // 按层扩散
            for (int i = 0; i < size; i++) {
                int pos = queue.removeFirst();
 
                int x = pos / col;
                int y = pos % col;
 
                for (int[] offset : offsets) {
                    // 上，下，左，右四个方向扩散
                    int newX = x + offset[0];
                    int newY = y + offset[1];
 
                    // 如果新位置没有越界，且为NO，则可以被改造
                    if (newX >= 0
                            && newX < row
                            && newY >= 0
                            && newY < col
                            && "NO".equals(matrix.get(newX)[newY])) {
                        matrix.get(newX)[newY] = "YES";
                        queue.add(newX * col + newY);
                        need--;
                    }
                }
            }
 
            day++;
        }
 
        if (need == 0) {
            return day;
        } else {
            return -1;
        }
    }

}
